<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  
  <title>Transformer家族之Insertion Transformer | Rogerspy&#39;s Home</title>
  
  <meta name="keywords" content="Machine Learning, Deep Learning, NLP">
  
  

  
  <link rel="alternate" href="/atom.xml" title="Rogerspy's Home">
  

  <meta name="HandheldFriendly" content="True">
  <meta name="apple-mobile-web-app-capable" content="yes">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <!-- meta -->
  
  
  <meta name="theme-color" content="#FFFFFF">
  <meta name="msapplication-TileColor" content="#1BC3FB">
  <meta name="msapplication-config" content="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicons/browserconfig.xml">
  

  <!-- link -->
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.css">
  
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/node-waves@0.7.6/dist/waves.min.css">
  
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.10.1/css/all.min.css">
  
  
  <link rel="shortcut icon" type="image/x-icon" href="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicon.ico">
  <link rel="icon" type="image/x-icon" sizes="32x32" href="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicons/favicon-32x32.png">
  <link rel="apple-touch-icon" type="image/png" sizes="180x180" href="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicons/apple-touch-icon.png">
  <link rel="mask-icon" color="#1BC3FB" href="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicons/safari-pinned-tab.svg">
  <link rel="manifest" href="https://cdn.jsdelivr.net/gh/xaoxuu/assets@master/favicon/favicons/site.webmanifest">
  

  

  
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-material-x@19.5/css/style.css">
  

  <script>
    function setLoadingBarProgress(num) {
      document.getElementById('loading-bar').style.width=num+"%";
    }
  </script>
  

  
  
  <!-- 时间线 -->
  <link rel="stylesheet" href="/css/timeline.css">
  <!-- 血小板-->
  <link rel="stylesheet" href="/live2d/css/live2d.css">
  <style>
	.article p .mjx-math {
	    font-family: Menlo,Monaco,courier,monospace,"Lucida Console",'Source Code Pro',"Microsoft YaHei",Helvetica,Arial,sans-serif,Ubuntu;
        background: none;
        padding: 2px;
        border-radius: 4px;
	}
  </style>
</head>

<body>
  
  
  <div class="cover-wrapper">
    <cover class='cover post half'>
      
        
  <h1 class='title'>Rogerspy's Home</h1>


  <div class="m_search">
    <form name="searchform" class="form u-search-form">
      <input type="text" class="input u-search-input" placeholder="" />
      <i class="icon fas fa-search fa-fw"></i>
    </form>
  </div>

<div class='menu navgation'>
  <ul class='h-list'>
    
      
        <li>
          <a class="nav home" href="/"
            
            
            id="home">
            <i class='fas fa-edit fa-fw'></i>&nbsp;博文
          </a>
        </li>
      
        <li>
          <a class="nav home" href="/video/"
            
            
            id="video">
            <i class='fas fa-film fa-fw'></i>&nbsp;视频
          </a>
        </li>
      
        <li>
          <a class="nav home" href="/material/"
            
              rel="nofollow"
            
            
            id="material">
            <i class='fas fa-briefcase fa-fw'></i>&nbsp;资料
          </a>
        </li>
      
        <li>
          <a class="nav home" href="/about/"
            
              rel="nofollow"
            
            
            id="about">
            <i class='fas fa-info-circle fa-fw'></i>&nbsp;关于
          </a>
        </li>
      
    
  </ul>
</div>

      
    </cover>
    <header class="l_header pure">
  <div id="loading-bar-wrapper">
    <div id="loading-bar" class="pure"></div>
  </div>

	<div class='wrapper'>
		<div class="nav-main container container--flex">
      <a class="logo flat-box" href='/' >
        
          Rogerspy's Home
        
      </a>
			<div class='menu navgation'>
				<ul class='h-list'>
          
  					
  						<li>
								<a class="nav flat-box" href="/blog/"
                  
                  
                  id="blog">
									<i class='fas fa-edit fa-fw'></i>&nbsp;博客
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/video/"
                  
                  
                  id="video">
									<i class='fas fa-film fa-fw'></i>&nbsp;视频小站
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/material/"
                  
                  
                  id="material">
									<i class='fas fa-briefcase fa-fw'></i>&nbsp;学习资料
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/diary/"
                  
                  
                  id="diary">
									<i class='fas fa-book fa-fw'></i>&nbsp;随心记
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/categories/"
                  
                    rel="nofollow"
                  
                  
                  id="categories">
									<i class='fas fa-folder-open fa-fw'></i>&nbsp;分类
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/tags/"
                  
                    rel="nofollow"
                  
                  
                  id="tags">
									<i class='fas fa-hashtag fa-fw'></i>&nbsp;标签
								</a>
							</li>
      			
  						<li>
								<a class="nav flat-box" href="/blog/archives/"
                  
                    rel="nofollow"
                  
                  
                  id="blogarchives">
									<i class='fas fa-archive fa-fw'></i>&nbsp;归档
								</a>
							</li>
      			
      		
				</ul>
			</div>

			
				<div class="m_search">
					<form name="searchform" class="form u-search-form">
						<input type="text" class="input u-search-input" placeholder="搜索" />
						<i class="icon fas fa-search fa-fw"></i>
					</form>
				</div>
			
			<ul class='switcher h-list'>
				
					<li class='s-search'><a class="fas fa-search fa-fw" href='javascript:void(0)'></a></li>
				
				<li class='s-menu'><a class="fas fa-bars fa-fw" href='javascript:void(0)'></a></li>
			</ul>
		</div>

		<div class='nav-sub container container--flex'>
			<a class="logo flat-box"></a>
			<ul class='switcher h-list'>
				<li class='s-comment'><a class="flat-btn fas fa-comments fa-fw" href='javascript:void(0)'></a></li>
        
          <li class='s-toc'><a class="flat-btn fas fa-list fa-fw" href='javascript:void(0)'></a></li>
        
			</ul>
		</div>
	</div>
</header>
	<aside class="menu-phone">
    <header>
		<nav class="menu navgation">
      <ul>
        
          
            <li>
							<a class="nav flat-box" href="/"
                
                
                id="home">
								<i class='fas fa-clock fa-fw'></i>&nbsp;近期文章
							</a>
            </li>
          
            <li>
							<a class="nav flat-box" href="/blog/archives/"
                
                  rel="nofollow"
                
                
                id="blogarchives">
								<i class='fas fa-archive fa-fw'></i>&nbsp;文章归档
							</a>
            </li>
          
            <li>
							<a class="nav flat-box" href="/blog/"
                
                
                id="blog">
								<i class='fas fa-edit fa-fw'></i>&nbsp;我的博客
							</a>
            </li>
          
            <li>
							<a class="nav flat-box" href="/video/"
                
                  rel="nofollow"
                
                
                id="video">
								<i class='fas fa-film fa-fw'></i>&nbsp;我的视频
							</a>
            </li>
          
            <li>
							<a class="nav flat-box" href="/material/"
                
                  rel="nofollow"
                
                
                id="material">
								<i class='fas fa-briefcase fa-fw'></i>&nbsp;学习资料
							</a>
            </li>
          
            <li>
							<a class="nav flat-box" href="/about/"
                
                  rel="nofollow"
                
                
                id="about">
								<i class='fas fa-info-circle fa-fw'></i>&nbsp;关于小站
							</a>
            </li>
          
       
      </ul>
		</nav>
    </header>
	</aside>
<script>setLoadingBarProgress(40);</script>

  </div>


  <div class="l_body">
    <div class='body-wrapper'>
      <div class='l_main'>
  

  
    <article id="post" class="post white-box article-type-post" itemscope itemprop="blogPost">
      


  <section class='meta'>
    
    
    <div class="meta" id="header-meta">
      
        
  
    <h1 class="title">
      <a href="/2020/04/09/transformer家族-insert/">
        Transformer家族之Insertion Transformer
      </a>
    </h1>
  


      
      <div class='new-meta-box'>
        
          
        
          
            
  <div class='new-meta-item author'>
    <a href="https://rogerspy.gitee.io" rel="nofollow">
      
        <i class="fas fa-user" aria-hidden="true"></i>
      
      <p>Rogerspy</p>
    </a>
  </div>


          
        
          
            <div class="new-meta-item date">
  <a class='notlink'>
    <i class="fas fa-calendar-alt" aria-hidden="true"></i>
    <p>2020-04-09</p>
  </a>
</div>

          
        
          
            
  
  <div class='new-meta-item category'>
    <a href='/categories/nlp/' rel="nofollow">
      <i class="fas fa-folder-open" aria-hidden="true"></i>
      <p>NLP</p>
    </a>
  </div>


          
        
          
            
  
    <div class="new-meta-item browse busuanzi">
      <a class='notlink'>
        <i class="fas fa-eye" aria-hidden="true"></i>
        <p>
          <span id="busuanzi_value_page_pv">
            <i class="fas fa-spinner fa-spin fa-fw" aria-hidden="true"></i>
          </span>
        </p>
      </a>
    </div>
  


          
        
          
            

          
        
          
            
  
    <div style="margin-right: 10px;">
      <span class="post-time">
        <span class="post-meta-item-icon">
          <i class="fa fa-keyboard"></i>
          <span class="post-meta-item-text">  字数统计: </span>
          <span class="post-count">4.1k字</span>
        </span>
      </span>
      &nbsp; | &nbsp;
      <span class="post-time">
        <span class="post-meta-item-icon">
          <i class="fa fa-hourglass-half"></i>
          <span class="post-meta-item-text">  阅读时长≈</span>
          <span class="post-count">17分</span>
        </span>
      </span>
    </div>
  

          
        
      </div>
      
        <hr>
      
    </div>
  </section>


      <section class="article typo">
        <div class="article-entry" itemprop="articleBody">
          <p><img src="https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/5396ee05ly1g5pqn3ch6zj20u092znph.jpg" alt></p>
<p>传统的文本生成，比如机器翻译无论是自回归或者半自回归的推理方式，都有一个特点：通常是自左向右依次生成文本序列。本文将介绍一篇文章，打破思维定式，突破自左向右的顺序生成。<em>Insertion Transformer</em>采用随机插入式序列生成：</p>
<ul>
<li>以任意顺序生成；</li>
<li>支持自回归或者半自回归生成（同时在不同位置插入）。</li>
</ul>
<p><em>Insertion Transformer</em>不仅在效果上远超非自回归模型，而且能以$log(n)$的推理速度，效果上达到原始<em>Transformer</em>的水平。</p>
<a id="more"></a>
<h1 id="1-Abstract-Framework"><a href="#1-Abstract-Framework" class="headerlink" title="1. Abstract Framework"></a>1. Abstract Framework</h1><ul>
<li>$x$ —— 源序列</li>
<li>$y$ —— 目标序列</li>
<li>$\hat{y}_t$ —— $t$ 时刻的输出序列，由于我们只有插入操作，因此 $\hat{y}_t$ 必须是最终输出序列的子序列，比如如果最终输出序列是$[A, B, C, D, E, F]$，那么$\hat{y}_t=[B, C]$ 是合法的，而$[C, B]$则不可以</li>
<li>$\hat{y}$ —— 最终输出序列</li>
<li>$C$ —— 词表</li>
<li>$c$ —— $c \in C$，上下文</li>
<li>$l$ —— $l \in [0, |\hat{y}_t|]$，需要插入词的位置</li>
</ul>
<p><em>Insertion Transformer</em> 需要对输出的词和词的位置都要进行建模：</p>
<script type="math/tex; mode=display">
p(c, l|x, \hat{y}_t) = \mathrm{InsertionTransformer}(x, \hat{y}_t)</script><p>举个例子：</p>
<p>假设$\hat{y}_t = [B, D]$，$p(c, l| x, \hat{y}_t) = (c=C, l=1)$，也就是说把 $C$ 插入到 $\hat{y}_t$的 索引值为1的地方（从0开始计算索引），这就意味着$\hat{y}_{t+1} = [B, C, D]$。</p>
<h1 id="2-Insertion-Transformer"><a href="#2-Insertion-Transformer" class="headerlink" title="2. Insertion Transformer"></a>2. Insertion Transformer</h1><ul>
<li><strong>Full Decoder Self-Attention</strong></li>
</ul>
<p>将 <em>Transformer</em> 中的 <em>causal self-attention</em> 替换为 <em>full self-attention</em>。</p>
<ul>
<li><strong>Slot Representation via Concatenated Outputs</strong></li>
</ul>
<p>标准的 <em>Transformer</em> 是给输入 $n$ 个词，然后模型输出 $n$ 个向量，然后取最后一个词作为输出序列的下一个词。而为了实现插入操作，作者对 <em>decoder</em> 做了修改。因为插入需要的是在词与词之间插入，也就是说，<em>decoder</em> 需要对<em>slot</em> 进行编码，$n$ 个词就有 $n+1$ 个 <em>slot</em>，也就是说给定 $n$ 个词，<em>decoder</em> 输出必须是 $n+1$ 个向量：$n$ 个词之间有 $n-1$ 个<em>slot</em>，而序列开始和结束的地方还有两个 <em>slot</em>，一共 $n+1$ 个<em>slot</em>。</p>
<p>比如：$[A, C, E]$  一共有3个词，$A, C$和$C, E$之间两个<em>slot</em>，模型下一个预测的词也有可能需要插入到$A$之前，或者 $B$ 之后，所以 $A$ 前和 $B$ 后还有两个<em>slot</em>，3个词4个 <em>slot</em>。</p>
<p>为了实现这一目标，我们在 <em>decoder</em> 的输入序列上加入特殊的开始和结束符，比如<code>&lt;BOS&gt;</code>或者<code>&lt;EOS&gt;</code>。这样我们就构造了一个 $n+2$ 的输入序列，最终 <em>decoder</em> 也将输出 $n+2$ 个向量。然后我们再将相邻的两个向量拼接在一起，这样就形成了 $n+1$ 个向量了。每个向量代表一个 <em>slot</em>。因此，每个 <em>slot</em> 相当于综合了该位置前后两个词的语义。</p>
<p>举个例子：</p>
<ol>
<li>给定 $[A, C, E]$；</li>
<li>加入 <code>&lt;BOS&gt;</code> 和 <code>&lt;EOS&gt;</code>，成为 $[&lt; BOS &gt;, A, C, E, &lt; EOS &gt;]$；</li>
<li>输入给<em>decoder</em>；</li>
<li><em>decoder</em> 输出 $[[1,2,3], [2,3,4], [3,4,5], [4,5,6], [5,6,7]]$；</li>
<li>将相邻的两个向量拼接起来：$[[1,2,3,2,3,4],[2,3,4,3,4,5],[3,4,5,4,5,6],[4,5,6,5,6,7]]$;</li>
</ol>
<h2 id="2-1-Model-Variants"><a href="#2-1-Model-Variants" class="headerlink" title="2.1 Model Variants"></a>2.1 Model Variants</h2><p>得到了 <em>slot</em> 向量，怎样得到最终的 $p(c, l)$，作者对此也进行了一番探索。</p>
<p>在继续介绍之前，我们先定义一些变量：</p>
<ul>
<li>$H$ —— $H \in \mathbb{R}^{(T+1) \times d}$，表示上面我们得到的 <em>slot</em> 特征矩阵， 其中 $d$ 是向量维度，$T$ 是输入序列长度；</li>
<li>$W$ —— $W \in \mathbb{R}^{d \times |C|}$，是标准的 <em>softmax</em> 投影矩阵，其中 $|C|$ 表示词表大小。</li>
</ul>
<p>好了，我们继续下面的介绍。</p>
<ul>
<li><strong>Content-Location Distribution</strong></li>
</ul>
<p>为了得到 $p(c, l|x, \hat{y}_t)$，作者提出两种方法：第一种是直接对 $(\mathrm{content}, \mathrm{slot})$进行建模；另一种方式是因式分解。</p>
<ol>
<li>直接建模</li>
</ol>
<script type="math/tex; mode=display">
p(c, l) = \mathrm{softmax}(\mathrm{flatten}(HW))</script><p>注意这里得到的是一个$(T+1) \times |C|$ 的矩阵，其物理意义为：在$(T+1)$ 个<em>slot</em> 的每个位置上最可能出现的词。</p>
<ol>
<li>因式分解</li>
</ol>
<p>我们可以利用条件因式分解得到：</p>
<script type="math/tex; mode=display">
p(c, l) = p(c|l) \cdot p(l) \\\\
p(c|l) = \mathrm{softmax}(h_l \cdot W) \\\\
p(l) = \mathrm{softmax}(H \cdot q)</script><p>其中 $h_l \in \mathbb{R}^{d}$ 表示 $H$ 的第 $l$ 行，$q \in \mathbb{R}^{d}$ 表示一个可学习的 <em>query</em> 向量。</p>
<p>这种方法的好处是相对直接建模的方式内存消耗要小得多。</p>
<ul>
<li><strong>Contextualized Vocabulary Bias</strong></li>
</ul>
<p>为了增加 <em>slot</em> 之间的信息共享，我哦们可以在 $H$ 上增加一个最大池化的操作，得到一个上下文向量 $g \in \mathbb{R}^d$，然后用一个可学习的投影矩阵  $V \in \mathbb{R}^{d \times |C|}$ 将 $g$ 投影到词表空间: $b=g \cdot V \in \mathbb{R}^{|C|}$，将 $b$ 作为偏置量添加到每个位置上。整个过程如下：</p>
<script type="math/tex; mode=display">
g = \mathrm{maxpool}(H) \\\\
b = g \cdot V \\\\
B = \mathrm{repmat}(b, [T+1, 1]) \\\\
p(c, l) = \mathrm{softmax}(HW+B)</script><ul>
<li><strong>Mixtrue-of-Softmaxes Output Layer (Optional)</strong></li>
</ul>
<p>讲道理，这部分我没有太想明白为什么需要 <em>MoS</em>。如果是从语言模型本身的复杂性来考虑，<em>MoS</em> 确实有可能会起到效果， 但是如果从同时编码 $(c, l)$ 的角度考虑的话，我就不太明白了。从文章的实验结果来看，这部分修改并没有使模型达到最佳效果（当然如果只考虑以上三种变种的话，加上 <em>MoS</em> 确实有提升效果，但是加上后续的一些 <em>tricks</em> 综合整个模型试验，它并没有达到最佳效果）。因此，这里对 <em>MoS</em> 做简单介绍吧，更详细的内容请去读<a href="https://arxiv.org/pdf/1711.03953.pdf" target="_blank" rel="noopener">原文</a>。</p>
<p>假设我们有一个上下文矩阵 $H \in \mathbb{R}^{N \times d}$，一个词向量矩阵 $W \in \mathbb{R}^{|C| \times d}$，其中 $|C|$ 是词表大小。给定上下文，我们希望从矩阵 $A$ 中去预测下一个词 $p(x|c)$，其中 $A \in \mathbb{R}^{N \times |C|}$。我们的模型是希望通过从真实的世界中采样 $N$ 个样本，训练出尽可能接近 $A$ 分布的 $A’$ 矩阵。</p>
<script type="math/tex; mode=display">
H = \left[
\begin{array}{c}
\mathbf{h}_{c1}^T\\\\
\vdots \\\\
\mathbf{h}_{cN}^T
\end{array}
\right];
W = \left[
\begin{array}{c}
\mathbf{w}_{x1}^T\\\\
\vdots \\\\
\mathbf{w}_{xM}^T
\end{array}
\right];
A = \left[
\begin{array}{ccc}
\log p(x_1|c_1), & \cdots, & \log p(x_M|c_1)\\\\
\vdots , & \ddots, & \vdots\\\\
\log p(x_1|c_N), & \cdots, & \log p(x_M|c_N),
\end{array}
\right]</script><p>我们希望 $A’ = HW^T$，尽量接近 $A$ 的分布。</p>
<p>矩阵乘法有一个性质：两矩阵乘积的秩（<em>rank</em>）等于两个矩阵秩较小的那个：</p>
<script type="math/tex; mode=display">
\mathrm{rank}(A \cdot B) = \min(\mathrm{rank}(A), \mathrm{rank}(B))</script><p>通常我们的训练样本 $N$ 会远远大于词向量的维度，也就是说 $A’$ 的秩的上限由词向量维度 $h$ 决定的。而真实世界的 $A$ 的秩很可能接近 $|C|$，通常 $|C| \gg d$。这就造成一个问题，我们希望通过 $A’$ 来逼近 $A$ 的分布，但是实际上$A’$ 的秩是远低于 $A$ 的，也就是说我们的模型训练出来的矩阵表达能力是远低于真实世界的。</p>
<p><strong>简单一句话就是：由于词向量维度的限制，我们训练出来的模型表达能力不足以完整的描述真实的世界。</strong></p>
<p>要解决这个问题的最直接的方法就是让词向量的维度等于词表的大小，即 $d = |C|$。但这会引入另外一个问题，那就是<strong>参数量爆炸！</strong>。</p>
<p>因此，作者提出 <em>Mixture of Softmax</em>:</p>
<script type="math/tex; mode=display">
[\mathbf{h}_0, ..., \mathbf{h}_K] = \tanh(\mathbf{h}P^T)</script><script type="math/tex; mode=display">
[\pi_0, ..., \pi_K] = \mathrm{softmax}(\mathbf{h}M^T)</script><script type="math/tex; mode=display">
P_{\theta}(x|\mathbf{h}) = \sum_{k=1}^{K}\pi_{c, k} \frac{\exp(\mathbf{h}_{c, k}^T \mathbf{w}_x)}{\sum_{x' \exp(\mathbf{h}_{c, k}^T \mathbf{w}_{x'})}}</script><p>其中 $\sum_{k=1}^K\pi_{c, k}=1$。</p>
<p>这里引入了两个权重：</p>
<ul>
<li>$P \in \mathbb{R}^{Kd\times d}$，它将 $\mathbf{h}$ 映射成 $K$ 个不同的 $\mathbf{h}$，每个 $\mathbf{h_k} \in \mathbb{R}^d$；</li>
<li>$M \in \mathbb{R}^{d \times K}$，决定这 $K$ 个模型如何混合。</li>
</ul>
<p>这个模型的基本原理就相当于使用 $K$ 个 <em>softmax</em> 将它们混合起来，既避免了参数量爆炸，又保持了模型的表达能力。这 $K$ 个不同的模型组合求加权平均效果往往比单一的模型要好， $K$ 个模型联合训练也能避免一些单模型的缺陷。</p>
<h1 id="3-Training-and-Loss-Functions"><a href="#3-Training-and-Loss-Functions" class="headerlink" title="3. Training and Loss Functions"></a>3. Training and Loss Functions</h1><p><em>Insertion Transformer</em>的机制支持它以任何顺序来生成目标语句，因此在训练时，可以通过设计<em>loss function</em>来将先验的顺序信息施加给模型，从而使得模型在预测时也按照先验的顺序进行预测。</p>
<h2 id="3-1-Left-to-Right"><a href="#3-1-Left-to-Right" class="headerlink" title="3.1 Left-to-Right"></a>3.1 Left-to-Right</h2><p>文中将原始自回归模型从左到右的生成方式作为一个特例进行对比。固定每次插入的单词位置都在最右侧，就退化成了原始的序列生成方式。</p>
<script type="math/tex; mode=display">
\mathrm{loss}(x, \hat{y}) = - \log p(y_{k+1}, k | x, \hat{y})</script><h2 id="3-2-Balanced-Binary-Tree"><a href="#3-2-Balanced-Binary-Tree" class="headerlink" title="3.2 Balanced Binary Tree"></a>3.2 Balanced Binary Tree</h2><p>显然从左到右的解码方式不能做到并行。因此，作者提出使用平衡二叉树的方式最大化并行解码能力。基本思想是：每次生成目标序列最中间的词。</p>
<p>比如，目标序列是 $[A, B, C, D, E, F, G]$，解码的顺序是：</p>
<ol>
<li>$[]$；</li>
<li>$[D]$；</li>
<li>$[B, D, F]$；</li>
<li>$[A, B, C, D, E, F, G]$。</li>
</ol>
<p>为了达到这个目的，作者提出 <em>soft binary tree loss</em>：</p>
<ol>
<li><p>随机挑选一个 $k$ 值，$k \sim \mathrm{uniform}(0, |y|)$；</p>
</li>
<li><p>打乱 $y$ 中每个词的索引顺序，选择其中前 $k$ 个索引对应的词，这样就得到了一个长度为 $k$ 的子序列；</p>
</li>
<li><p>这个长度为 $k$ 的子序列包含 $k+1$ 个<em>slot</em>，每个 <em>slot</em> 对应的位置为 $l = 0, 1, …, k$。令 $(y_{i_l}, y_{i_l+1}, …, y_{j_l})$为 $ y$ 中剩余的对应第 $l$ 个 <em>slot</em> 位置上的词。</p>
<p><img src="https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/20200410151034.png" alt></p>
<blockquote>
<p>以上图为例：解释$(y_{i_l}, y_{i_l+1}, …, y_{j_l})$是什么？$[A, C, D, I, M]$ 是随机挑选出来的子序列，</p>
<ul>
<li>$l=1$ 对应的 $(y_{i_1}, y_{i_1+1}, …, y_{j_1})=[B]$；</li>
<li>$l=3$ 对应的 $(y_{i_3}, y_{i_3+1}, …, y_{j_3})=[E, F, G, H]$；</li>
<li>$l=4$ 对应的 $(y_{i_4}, y_{i_4+1}, …, y_{j_4})=[J, K, L]$；</li>
<li>$l=5$ 对应的 $(y_{i_5}, y_{i_5+1}, …, y_{j_5})=[N, O]$；</li>
</ul>
<p>对于$l=0, 2$ 的情况在后面讨论。</p>
<p>注意 $i_l, j_l$ 分别是该词在原始 $y$ 中的索引。</p>
</blockquote>
<p>得到了 $(y_{i_l}, y_{i_l+1}, …, y_{j_l})$ 列表以后，我们去计算每个 <em>slot</em> 与其对应的$(y_{i_l}, y_{i_l+1}, …, y_{j_l})$ 中每个词的距离：</p>
<script type="math/tex; mode=display">
d_l(i) = \left|\frac{i_l+j_l}{2}-i\right|</script><blockquote>
<ul>
<li><p>$l=1$ : $d_1 = \left|\frac{1+1}{2}-i|_{i=1}\right| = [0]$；</p>
</li>
<li><p>$l=3$ : $d_3 = \left|\frac{4+7}{2}-i|_{i=4,5,6,7}\right| = [1.5, 0.5, 0.5, 1.5]$；</p>
</li>
<li>$l=4$ : $d_4 = \left|\frac{9+11}{2}-i|_{i=9,10,11}\right| = [1,0,1]$；</li>
<li>$l=5$ : $d_5 = \left|\frac{13+14}{2}-i|_{i=13,14}\right| = [0.5, 0.5]$；</li>
</ul>
</blockquote>
<p>然后我们根据上面计算出来的距离，给每个距离一个权重：</p>
<script type="math/tex; mode=display">
w_l(i) = \frac{\exp(-d_l(i)/\tau)}{\sum_{i^{'}}^{j_l}\exp(-d_l(i^{'})/\tau)}</script></li>
<li><p>有了上面的权重，我们就可以定义每个位置上的 <em>slot loss</em> 了：</p>
<script type="math/tex; mode=display">
\mathrm{SlotLoss}(x, \hat{y}, l)=\sum_{i=i_l}^{j_l} -\log p(y_i, l|x, \hat{y}) \cdot w_l(i)</script></li>
<li><p>最后总的 <em>loss</em> 为：</p>
<script type="math/tex; mode=display">
\mathrm{loss} = \frac{1}{k+1}\sum_{l=0}^k \mathrm{SlotLoss}(x, \hat{y}, l)</script></li>
</ol>
<p><em>SlotLoss</em> 中的 $\tau$ 是一个温度超参数，用来控制 $w_l$ 的平滑程度的：当 $\tau \rightarrow 0$ 时，将会给最中间的位置以非常高的权重，两侧的位置权重几乎为 0；当 $\tau \rightarrow \infty$ 时，每个位置的权重基本相等。</p>
<h2 id="3-3-Uniform"><a href="#3-3-Uniform" class="headerlink" title="3.3 Uniform"></a>3.3 Uniform</h2><p>作者也做了不给模型施加约束，让模型自己探索生成方式的尝试，即鼓励模型uniform地生成每个slot中的各个单词。实现的方式很简单，将$\tau \rightarrow \infty$ 即可。</p>
<h2 id="3-4-Termination-Condition"><a href="#3-4-Termination-Condition" class="headerlink" title="3.4 Termination Condition"></a>3.4 Termination Condition</h2><p>选取解码时的停止条件也是一个很关键的问题。<em>Insertion Transformer</em> 提出了两种停止条件:</p>
<ul>
<li><p><em>Slot Finalization</em> 在训练时引入了 <em>end-of-slot token</em>，来和 <em>label</em> 为空的 <em>slot</em> 计算损失函数。在推理时，当且仅当<strong>全部</strong> <em>slot</em> 的预测都为 <em>end-of-slot</em> 时，停止继续解码。</p>
<blockquote>
<p>上面我们在介绍 <em>soft binary tree loss</em> 的时候遗留了一个问题：$l=0, 2$ 时怎么办？我们看到当 $l=0, 2$ 时我们不需要插入任何词，这时候我们定义一个 <em>end-of-slot token</em>，这个时候 $l=0, 2$ 对应的 $(y_{i_1}, y_{i_1+1}, …, y_{j_1})=[\mathrm{EndOfSlot}]$ ，然后我们用 $\mathrm{EndOfSlot}$ 计算损失。推理的时候，当所有的 <em>slot</em> 对应的 $y_{i_l}$ 都是  $\mathrm{EndOfSlot}$ 时停止解码。</p>
</blockquote>
</li>
<li><p><em>Sequence Finalization</em> 则还是用的传统的 <em>end-of-sequence token</em>，在全部单词都生成之后，将每个 <em>slot</em> 都和 <em>end-of-sequence token</em> 计算损失函数。在推理时，当<strong>任意</strong>一个 <em>slot</em> 的预测结果是 <em>end-of-sequence token</em> 时，停止解码。</p>
<blockquote>
<p>回到上面那个 $l=0, 2$ 的问题，在上面使用 <em>Slot Finalization</em> 时，我们令 $(y_{i_1}, y_{i_1+1}, …, y_{j_1})=[\mathrm{EndOfSlot}]$ 然后计算相关损失。当使用 <em>Sequence Finalization</em> 时，遇到 $l=0, 2$ 这种情况的时候，我们认为这里需要插入空字符串，跳过这两个位置的损失计算。直到所有的 <em>slot</em> 都不再产生损失（也就是所有 <em>slot</em> 都要插入空字符串）的时候，我们让每个 <em>slot</em> 都和 <em>end-of-sequence token</em> 计算损失。推理的时候，任意一个 <em>slot</em> 的预测是 <em>end-of-sequence token</em> 则停止解码。</p>
</blockquote>
</li>
</ul>
<h1 id="4-Inference"><a href="#4-Inference" class="headerlink" title="4. Inference"></a>4. Inference</h1><h2 id="4-1-Greedy-Decoding"><a href="#4-1-Greedy-Decoding" class="headerlink" title="4.1 Greedy Decoding"></a>4.1 Greedy Decoding</h2><p><em>Greedy decoding</em> 支持 <em>Slot Finalization</em> 和 <em>Sequence Finalization</em> 两种终止条件的训练模式。推理的时候选择概率最高的词和对应的位置：</p>
<script type="math/tex; mode=display">
(\hat{c}_t, \hat{l}_t) = \arg \max p(c, l|x, \hat{y})</script><p>然后再 $\hat{l}_t$ 位置上插入 $\hat{c}_t$。</p>
<h2 id="4-2-Parallel-Decoding"><a href="#4-2-Parallel-Decoding" class="headerlink" title="4.2 Parallel Decoding"></a>4.2 Parallel Decoding</h2><p>采用 <em>Slot Finalization</em> 方式支持并行训练和解码。具体来说，就是对于每个 <em>slot</em> 计算最高概率的词：</p>
<script type="math/tex; mode=display">
\hat{c}_{l, t} = \arg \max p(c | l,x,\hat{y}_t)</script><p>这样相当于每次推理我们能填满所有 <em>slot</em>，理论上，只需要 $\log_2(n)+1$ 步就可以生成一个长度为 $n$ 的序列。</p>
<h1 id="5-Tricks"><a href="#5-Tricks" class="headerlink" title="5. Tricks"></a>5. Tricks</h1><p>作者对模型做了非常充分的实验，也做了很多有意思的讨论。这里总结一些比较有用的小 <em>tricks</em>：</p>
<ul>
<li>由于两种终止条件在训练的时候引入了过多的 $&lt; EOS &gt;$, 会导致模型在推理时很容易生成 $&lt; EOS &gt;$造成早停的问题。因此文章引入了 $&lt; EOS &gt;$  惩罚来在推理时对   $&lt; EOS &gt;$ 人为地增加预测难度：仅当   $&lt; EOS &gt;$ 的概率大于第二可能单词的概率一个阈值 $\beta$ 的时候才会真正生成 $&lt; EOS &gt;$。从实验中看来，这是一个很重要的 <em>trick</em>。</li>
<li>使用<em>base Transformer</em> 作为模型的 <em>teacher model</em>，来做知识蒸馏也会提升模型的能力。</li>
</ul>
<h1 id="6-Experiments"><a href="#6-Experiments" class="headerlink" title="6. Experiments"></a>6. Experiments</h1><p><img src="https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/20200410172118.png" alt></p>
<p>这个实验是分析 2.1 节讨论的模型的不同变种的效果。从结果上看，不加 $&lt; EOS &gt;$ 惩罚的时候，<code>Contextual + Mixture</code> 能达到最佳效果，但是加上惩罚之后这种效果提升就消失了。说明模型的核心结构在适当的调整下已经足够强大有效，无需做太大的调整。</p>
<p><img src="https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/20200410172252.png" alt></p>
<p>这个实验室采用并行解码的方式进行推理。我们发现之前介绍的平衡二叉树损失是非常有效的，另外$&lt; EOS &gt;$ 惩罚带来的提升已经不太明显了。</p>
<p><img src="https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/20200410172333.png" alt></p>
<p>最后，与其他模型相比较，<em>Insertion Transformer</em> 不仅在效率上提升巨大，而且在效果上也达到了与自回归模型相同的水准。这是一个非常令人兴奋的结果。</p>
<p>最后，下面这张图展示了 <em>Insertion Transformer</em> 的一个实际推理的例子。</p>
<p><img src="https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/20200410172424.png" alt></p>
<h1 id="Reference"><a href="#Reference" class="headerlink" title="Reference"></a>Reference</h1><ol>
<li><a href="https://arxiv.org/pdf/1902.03249.pdf" target="_blank" rel="noopener">Insertion Transformer: Flexible Sequence Generation via Insertion Operations</a>, <em>Mitchell Stern, William Chan,  Jamie Kiros, Jakob Uszkoreit,  2019, arXiv: 1902.03249</em></li>
<li><a href="https://arxiv.org/pdf/1711.03953.pdf" target="_blank" rel="noopener">Breaking The Softmax Bottleneck: a High-Rank RNN Language Model</a>, <em>Zhilin Yang , Zihang Dai, Ruslan Salakhutdinov, William W. Cohen, 2018, arXiv: 1711.03953</em></li>
<li><a href="https://github.com/kweonwooj/papers/issues/123" target="_blank" rel="noopener">Insertion Transformer: Flexible Sequence Generation via Insertion Operations #123</a>, <em>kweonwooj, Github Pages</em></li>
<li><a href="https://zhuanlan.zhihu.com/p/89209220" target="_blank" rel="noopener">Non-Autoregressive NMT: Insertion Transformer</a>, <em>Leo Guo</em>, 知乎</li>
<li><a href="https://zhuanlan.zhihu.com/p/73417154" target="_blank" rel="noopener">香侬读 | 按什么套路生成？基于插入和删除的序列生成方法</a>, 香侬科技, 知乎</li>
<li><a href="https://smerity.com/articles/2017/mixture_of_softmaxes.html" target="_blank" rel="noopener">Understanding the Mixture of Softmaxes (MoS)</a></li>
</ol>

        </div>
        
          


  <section class='meta' id="footer-meta">
    <hr>
    <div class='new-meta-box'>
      
        
          <div class="new-meta-item date" itemprop="dateUpdated" datetime="2021-08-23T01:05:27+08:00">
  <a class='notlink'>
    <i class="fas fa-clock" aria-hidden="true"></i>
    <p>最后更新于 2021年8月23日</p>
  </a>
</div>

        
      
        
          
  
  <div class="new-meta-item meta-tags"><a class="tag" href="/tags/transformer/" rel="nofollow"><i class="fas fa-hashtag" aria-hidden="true"></i>&nbsp;<p>Transformer</p></a></div> <div class="new-meta-item meta-tags"><a class="tag" href="/tags/nmt/" rel="nofollow"><i class="fas fa-hashtag" aria-hidden="true"></i>&nbsp;<p>NMT</p></a></div> <div class="new-meta-item meta-tags"><a class="tag" href="/tags/insertion/" rel="nofollow"><i class="fas fa-hashtag" aria-hidden="true"></i>&nbsp;<p>insertion</p></a></div>


        
      
        
          
  <div class="new-meta-item share -mob-share-list">
  <div class="-mob-share-list share-body">
    
      
        <a class="-mob-share-qq" title="QQ好友" rel="external nofollow noopener noreferrer"
          
          href="http://connect.qq.com/widget/shareqq/index.html?url=https://rogerspy.gitee.io/2020/04/09/transformer家族-insert/&title=Transformer家族之Insertion Transformer | Rogerspy's Home&summary=
传统的文本生成，比如机器翻译无论是自回归或者半自回归的推理方式，都有一个特点：通常是自左向右依次生成文本序列。本文将介绍一篇文章，打破思维定式，突破自左向右的顺序生成。Insertion Transformer采用随机插入式序列生成：

以任意顺序生成；
支持自回归或者半自回归生成（同时在不同位置插入）。

Insertion Transformer不仅在效果上远超非自回归模型，而且能以$log(n)$的推理速度，效果上达到原始Transformer的水平。"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/xaoxuu/assets@19.1.9/logo/128/qq.png">
          
        </a>
      
    
      
        <a class="-mob-share-qzone" title="QQ空间" rel="external nofollow noopener noreferrer"
          
          href="https://sns.qzone.qq.com/cgi-bin/qzshare/cgi_qzshare_onekey?url=https://rogerspy.gitee.io/2020/04/09/transformer家族-insert/&title=Transformer家族之Insertion Transformer | Rogerspy's Home&summary=
传统的文本生成，比如机器翻译无论是自回归或者半自回归的推理方式，都有一个特点：通常是自左向右依次生成文本序列。本文将介绍一篇文章，打破思维定式，突破自左向右的顺序生成。Insertion Transformer采用随机插入式序列生成：

以任意顺序生成；
支持自回归或者半自回归生成（同时在不同位置插入）。

Insertion Transformer不仅在效果上远超非自回归模型，而且能以$log(n)$的推理速度，效果上达到原始Transformer的水平。"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/xaoxuu/assets@19.1.9/logo/128/qzone.png">
          
        </a>
      
    
      
        <a class='qrcode' rel="external nofollow noopener noreferrer" href=''>
        
          <img src="https://cdn.jsdelivr.net/gh/xaoxuu/assets@19.1.9/logo/128/wechat.png">
        
        </a>
      
    
      
        <a class="-mob-share-weibo" title="微博" rel="external nofollow noopener noreferrer"
          
          href="http://service.weibo.com/share/share.php?url=https://rogerspy.gitee.io/2020/04/09/transformer家族-insert/&title=Transformer家族之Insertion Transformer | Rogerspy's Home&summary=
传统的文本生成，比如机器翻译无论是自回归或者半自回归的推理方式，都有一个特点：通常是自左向右依次生成文本序列。本文将介绍一篇文章，打破思维定式，突破自左向右的顺序生成。Insertion Transformer采用随机插入式序列生成：

以任意顺序生成；
支持自回归或者半自回归生成（同时在不同位置插入）。

Insertion Transformer不仅在效果上远超非自回归模型，而且能以$log(n)$的推理速度，效果上达到原始Transformer的水平。"
          
          >
          
            <img src="https://cdn.jsdelivr.net/gh/xaoxuu/assets@19.1.9/logo/128/weibo.png">
          
        </a>
      
    
  </div>
</div>



        
      
    </div>
  </section>


        
        
            <div class="prev-next">
                
                    <section class="prev">
                        <span class="art-item-left">
                            <h6><i class="fas fa-chevron-left" aria-hidden="true"></i>&nbsp;上一页</h6>
                            <h4>
                                <a href="/2020/04/16/transformer家族-kermit/" rel="prev" title="Transformer家族之KERMIT">
                                  
                                      Transformer家族之KERMIT
                                  
                                </a>
                            </h4>
                            
                                
                                <h6 class="tags">
                                    <a class="tag" href="/tags/transformer/"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i>Transformer</a> <a class="tag" href="/tags/nmt/"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i>NMT</a> <a class="tag" href="/tags/insertion/"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i>insertion</a>
                                </h6>
                            
                        </span>
                    </section>
                
                
                    <section class="next">
                        <span class="art-item-right" aria-hidden="true">
                            <h6>下一页&nbsp;<i class="fas fa-chevron-right" aria-hidden="true"></i></h6>
                            <h4>
                                <a href="/2020/03/30/transformer家族-sparse/" rel="prev" title="Transformer家族之Sparse Transformer">
                                    
                                        Transformer家族之Sparse Transformer
                                    
                                </a>
                            </h4>
                            
                                
                                <h6 class="tags">
                                    <a class="tag" href="/tags/transformer/"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i>Transformer</a> <a class="tag" href="/tags/nmt/"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i>NMT</a> <a class="tag" href="/tags/sparse/"><i class="fas fa-hashtag fa-fw" aria-hidden="true"></i>sparse</a>
                                </h6>
                            
                        </span>
                    </section>
                
            </div>
        
      </section>
    </article>
  

  
    <!-- 显示推荐文章和评论 -->



  <article class="post white-box comments">
    <section class="article typo">
      <h4><i class="fas fa-comments fa-fw" aria-hidden="true"></i>&nbsp;评论</h4>
      
      
      
        <section id="comments">
          <div id="gitalk-container"></div>
        </section>
      
      
    </section>
  </article>


  




<!-- 根据页面mathjax变量决定是否加载MathJax数学公式js -->

  <!-- MathJax配置，可通过单美元符号书写行内公式等 -->
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    "HTML-CSS": {
      preferredFont: "TeX",
      availableFonts: ["STIX","TeX"],
      linebreaks: { automatic:true },
      EqnChunk: (MathJax.Hub.Browser.isMobile ? 10 : 50)
    },
    tex2jax: {
      inlineMath: [ ["$", "$"], ["\\(","\\)"] ],
      processEscapes: true,
      ignoreClass: "tex2jax_ignore|dno",
      skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
    },
    TeX: {
      equationNumbers: { autoNumber: "AMS" },
      noUndefined: { attributes: { mathcolor: "red", mathbackground: "#FFEEEE", mathsize: "90%" } },
      Macros: { href: "{}" }
    },
    messageStyle: "none"
  });
</script>
<!-- 给MathJax元素添加has-jax class -->
<script type="text/x-mathjax-config">
  MathJax.Hub.Queue(function() {
    var all = MathJax.Hub.getAllJax(), i;
    for(i=0; i < all.length; i += 1) {
      all[i].SourceElement().parentNode.className += (all[i].SourceElement().parentNode.className ? ' ' : '') + 'has-jax';
    }
  });
</script>
<!-- 通过连接CDN加载MathJax的js代码 -->
<script type="text/javascript" async
  src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-MML-AM_CHTML">
</script>




  <script>
    window.subData = {
      title: 'Transformer家族之Insertion Transformer',
      tools: true
    }
  </script>


</div>
<aside class='l_side'>
  
    
    
      
        
          
          
            <section class='widget shake author'>
  <div class='content pure'>
    
      <div class='avatar'>
        <img class='avatar' src='https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/65-1Z31313530JC.jpeg'/>
      </div>
    
    
    
      <div class="social-wrapper">
        
          
            <a href="/atom.xml"
              class="social fas fa-rss flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
          
            <a href="mailto:rogerspy@163.com"
              class="social fas fa-envelope flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
          
            <a href="https://github.com/rogerspy"
              class="social fab fa-github flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
          
            <a href="https://music.163.com/#/user/home?id=1960721923"
              class="social fas fa-headphones-alt flat-btn"
              target="_blank"
              rel="external nofollow noopener noreferrer">
            </a>
          
        
      </div>
    
  </div>
</section>

          
        
      
        
          
          
            
  <section class='widget toc-wrapper'>
    
<header class='pure'>
  <div><i class="fas fa-list fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;本文目录</div>
  
    <div class='wrapper'><a class="s-toc rightBtn" rel="external nofollow noopener noreferrer" href="javascript:void(0)"><i class="fas fa-thumbtack fa-fw"></i></a></div>
  
</header>

    <div class='content pure'>
      <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#1-Abstract-Framework"><span class="toc-text">1. Abstract Framework</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#2-Insertion-Transformer"><span class="toc-text">2. Insertion Transformer</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#2-1-Model-Variants"><span class="toc-text">2.1 Model Variants</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#3-Training-and-Loss-Functions"><span class="toc-text">3. Training and Loss Functions</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#3-1-Left-to-Right"><span class="toc-text">3.1 Left-to-Right</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-2-Balanced-Binary-Tree"><span class="toc-text">3.2 Balanced Binary Tree</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-3-Uniform"><span class="toc-text">3.3 Uniform</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-4-Termination-Condition"><span class="toc-text">3.4 Termination Condition</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#4-Inference"><span class="toc-text">4. Inference</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#4-1-Greedy-Decoding"><span class="toc-text">4.1 Greedy Decoding</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#4-2-Parallel-Decoding"><span class="toc-text">4.2 Parallel Decoding</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#5-Tricks"><span class="toc-text">5. Tricks</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#6-Experiments"><span class="toc-text">6. Experiments</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#Reference"><span class="toc-text">Reference</span></a></li></ol>
    </div>
  </section>


          
        
      
        
          
          
            <section class='widget grid'>
  
<header class='pure'>
  <div><i class="fas fa-map-signs fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;站内导航</div>
  
</header>

  <div class='content pure'>
    <ul class="grid navgation">
      
        <li><a class="flat-box" " href="/"
          
          
          id="home">
          
            <i class="fas fa-clock fa-fw" aria-hidden="true"></i>
          
          近期文章
        </a></li>
      
        <li><a class="flat-box" " href="/blog/"
          
          
          id="blog">
          
            <i class="fas fa-edit fa-fw" aria-hidden="true"></i>
          
          我的博客
        </a></li>
      
        <li><a class="flat-box" " href="/paper_note/"
          
          
          id="paper_note">
          
            <i class="fas fa-book fa-fw" aria-hidden="true"></i>
          
          论文笔记
        </a></li>
      
        <li><a class="flat-box" " href="/algorithm/"
          
          
          id="algorithm">
          
            <i class="fas fa-cube fa-fw" aria-hidden="true"></i>
          
          算法基础
        </a></li>
      
        <li><a class="flat-box" " href="/leetcode/"
          
          
          id="leetcode">
          
            <i class="fas fa-code fa-fw" aria-hidden="true"></i>
          
          Leetcode
        </a></li>
      
        <li><a class="flat-box" " href="/video/"
          
          
          id="video">
          
            <i class="fas fa-film fa-fw" aria-hidden="true"></i>
          
          视频小站
        </a></li>
      
        <li><a class="flat-box" " href="/material/"
          
          
          id="material">
          
            <i class="fas fa-briefcase fa-fw" aria-hidden="true"></i>
          
          学习资料
        </a></li>
      
        <li><a class="flat-box" " href="/dataset/"
          
          
          id="dataset">
          
            <i class="fas fa-database fa-fw" aria-hidden="true"></i>
          
          数据集
        </a></li>
      
        <li><a class="flat-box" " href="/articles/"
          
          
          id="articles">
          
            <i class="fas fa-sticky-note fa-fw" aria-hidden="true"></i>
          
          杂文天地
        </a></li>
      
        <li><a class="flat-box" " href="/blog/archives/"
          
            rel="nofollow"
          
          
          id="blogarchives">
          
            <i class="fas fa-archive fa-fw" aria-hidden="true"></i>
          
          文章归档
        </a></li>
      
        <li><a class="flat-box" " href="/personal_center/"
          
          
          id="personal_center">
          
            <i class="fas fa-university fa-fw" aria-hidden="true"></i>
          
          个人中心
        </a></li>
      
        <li><a class="flat-box" " href="/about/"
          
            rel="nofollow"
          
          
          id="about">
          
            <i class="fas fa-info-circle fa-fw" aria-hidden="true"></i>
          
          关于小站
        </a></li>
      
    </ul>
  </div>
</section>

          
        
      
        
          
          
            <section class='widget list'>
  
<header class='pure'>
  <div><i class="fas fa-terminal fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;机器学习框架</div>
  
</header>

  <div class='content pure'>
    <ul class="entry">
      
        <li><a class="flat-box" title="https://rogerspy.gitee.io/pytorch-zh/" href="https://rogerspy.gitee.io/pytorch-zh/"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-star fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;PyTorch 中文文档
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://keras-zh.readthedocs.io/" href="https://keras-zh.readthedocs.io/"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-star fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Keras 中文文档
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://tensorflow.google.cn/" href="https://tensorflow.google.cn/"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-star fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Tensorflow 中文文档
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="http://scikitlearn.com.cn/" href="http://scikitlearn.com.cn/"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-star fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Scikit Learn 中文文档
          </div>
          
        </a></li>
      
    </ul>
  </div>
</section>

          
        
      
        
          
          
            <section class='widget list'>
  
<header class='pure'>
  <div><i class="fas fa-wrench fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;百宝箱</div>
  
</header>

  <div class='content pure'>
    <ul class="entry">
      
        <li><a class="flat-box" title="https://rogerspy.github.io/excalidraw-claymate/" href="https://rogerspy.github.io/excalidraw-claymate/"
          
          
            target="_blank"
          
          >
          <div class='name'>
            
              <i class="fas fa-magic fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Excalidraw-Claymate
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://rogerspy.github.io/jupyterlite/" href="https://rogerspy.github.io/jupyterlite/"
          
          
            target="_blank"
          
          >
          <div class='name'>
            
              <i class="fas fa-terminal fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;JupyterLite
          </div>
          
        </a></li>
      
    </ul>
  </div>
</section>

          
        
      
        
          
          
            <section class='widget list'>
  
<header class='pure'>
  <div><i class="fas fa-eye fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;睁眼看世界</div>
  
</header>

  <div class='content pure'>
    <ul class="entry">
      
        <li><a class="flat-box" title="https://deeplearn.org/" href="https://deeplearn.org/"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-link fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Deep Learning Monitor
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://paperswithcode.com/sota" href="https://paperswithcode.com/sota"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-link fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Browse State-of-the-Art
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://huggingface.co/transformers/" href="https://huggingface.co/transformers/"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-link fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Transformers
          </div>
          
        </a></li>
      
        <li><a class="flat-box" title="https://huggingface.co/models" href="https://huggingface.co/models"
          
          
          >
          <div class='name'>
            
              <i class="fas fa-link fa-fw" aria-hidden="true"></i>
            
            &nbsp;&nbsp;Transformers-models
          </div>
          
        </a></li>
      
    </ul>
  </div>
</section>

          
        
      
        
          
          
            
  <section class='widget category'>
    
<header class='pure'>
  <div><i class="fas fa-folder-open fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;文章分类</div>
  
    <a class="rightBtn"
    
      rel="nofollow"
    
    
    href="/categories/"
    title="categories/">
    <i class="fas fa-expand-arrows-alt fa-fw"></i></a>
  
</header>

    <div class='content pure'>
      <ul class="entry">
        
          <li><a class="flat-box" title="/categories/nl2sql/" href="/categories/nl2sql/"><div class='name'>NL2SQL</div><div class='badge'>(1)</div></a></li>
        
          <li><a class="flat-box" title="/categories/nlp/" href="/categories/nlp/"><div class='name'>NLP</div><div class='badge'>(23)</div></a></li>
        
          <li><a class="flat-box" title="/categories/博客转载/" href="/categories/博客转载/"><div class='name'>博客转载</div><div class='badge'>(5)</div></a></li>
        
          <li><a class="flat-box" title="/categories/数据结构与算法/" href="/categories/数据结构与算法/"><div class='name'>数据结构与算法</div><div class='badge'>(11)</div></a></li>
        
          <li><a class="flat-box" title="/categories/知识图谱/" href="/categories/知识图谱/"><div class='name'>知识图谱</div><div class='badge'>(3)</div></a></li>
        
          <li><a class="flat-box" title="/categories/论文解读/" href="/categories/论文解读/"><div class='name'>论文解读</div><div class='badge'>(2)</div></a></li>
        
          <li><a class="flat-box" title="/categories/语言模型/" href="/categories/语言模型/"><div class='name'>语言模型</div><div class='badge'>(10)</div></a></li>
        
      </ul>
    </div>
  </section>


          
        
      
        
          
          
            
  <section class='widget tagcloud'>
    
<header class='pure'>
  <div><i class="fas fa-fire fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;热门标签</div>
  
    <a class="rightBtn"
    
      rel="nofollow"
    
    
    href="/tags/"
    title="tags/">
    <i class="fas fa-expand-arrows-alt fa-fw"></i></a>
  
</header>

    <div class='content pure'>
      <a href="/tags/attention/" style="font-size: 16.86px; color: #868686">Attention</a> <a href="/tags/cnnlm/" style="font-size: 14px; color: #999">CNNLM</a> <a href="/tags/data-structure/" style="font-size: 14px; color: #999">Data Structure</a> <a href="/tags/deep/" style="font-size: 14px; color: #999">Deep</a> <a href="/tags/ffnnlm/" style="font-size: 14px; color: #999">FFNNLM</a> <a href="/tags/gaussian/" style="font-size: 14px; color: #999">Gaussian</a> <a href="/tags/initialization/" style="font-size: 14px; color: #999">Initialization</a> <a href="/tags/kg/" style="font-size: 16.86px; color: #868686">KG</a> <a href="/tags/lstm/" style="font-size: 14px; color: #999">LSTM</a> <a href="/tags/lstmlm/" style="font-size: 14px; color: #999">LSTMLM</a> <a href="/tags/language-model/" style="font-size: 16.86px; color: #868686">Language Model</a> <a href="/tags/log-linear-language-model/" style="font-size: 14px; color: #999">Log-Linear Language Model</a> <a href="/tags/nlp/" style="font-size: 19.71px; color: #727272">NLP</a> <a href="/tags/nmt/" style="font-size: 22.57px; color: #5f5f5f">NMT</a> <a href="/tags/norm/" style="font-size: 14px; color: #999">Norm</a> <a href="/tags/probabilistic-language-model/" style="font-size: 14px; color: #999">Probabilistic Language Model</a> <a href="/tags/rnnlm/" style="font-size: 14px; color: #999">RNNLM</a> <a href="/tags/roc-auc/" style="font-size: 14px; color: #999">ROC-AUC</a> <a href="/tags/transformer/" style="font-size: 24px; color: #555">Transformer</a> <a href="/tags/context2vec/" style="font-size: 14px; color: #999">context2vec</a> <a href="/tags/divide-conquer/" style="font-size: 14px; color: #999">divide-conquer</a> <a href="/tags/insertion/" style="font-size: 16.86px; color: #868686">insertion</a> <a href="/tags/insertion-deletion/" style="font-size: 15.43px; color: #8f8f8f">insertion-deletion</a> <a href="/tags/knowledge-modelling/" style="font-size: 15.43px; color: #8f8f8f">knowledge-modelling</a> <a href="/tags/nl2infographic/" style="font-size: 14px; color: #999">nl2infographic</a> <a href="/tags/nl2sql/" style="font-size: 14px; color: #999">nl2sql</a> <a href="/tags/ontology/" style="font-size: 14px; color: #999">ontology</a> <a href="/tags/parallel-recurrent/" style="font-size: 14px; color: #999">parallel-recurrent</a> <a href="/tags/pytorch/" style="font-size: 14px; color: #999">pytorch</a> <a href="/tags/queue/" style="font-size: 18.29px; color: #7c7c7c">queue</a> <a href="/tags/sparse/" style="font-size: 14px; color: #999">sparse</a> <a href="/tags/stack/" style="font-size: 14px; color: #999">stack</a> <a href="/tags/tensorflow/" style="font-size: 14px; color: #999">tensorflow</a> <a href="/tags/text2viz/" style="font-size: 14px; color: #999">text2viz</a> <a href="/tags/weighted-head/" style="font-size: 14px; color: #999">weighted-head</a> <a href="/tags/半监督语言模型/" style="font-size: 14px; color: #999">半监督语言模型</a> <a href="/tags/双数组前缀树/" style="font-size: 14px; color: #999">双数组前缀树</a> <a href="/tags/推荐系统/" style="font-size: 14px; color: #999">推荐系统</a> <a href="/tags/数据结构/" style="font-size: 21.14px; color: #686868">数据结构</a> <a href="/tags/数组/" style="font-size: 14px; color: #999">数组</a> <a href="/tags/时间复杂度/" style="font-size: 14px; color: #999">时间复杂度</a> <a href="/tags/算法/" style="font-size: 14px; color: #999">算法</a> <a href="/tags/评估方法/" style="font-size: 14px; color: #999">评估方法</a> <a href="/tags/词向量/" style="font-size: 14px; color: #999">词向量</a> <a href="/tags/隐式正则化/" style="font-size: 14px; color: #999">隐式正则化</a>
    </div>
  </section>


          
        
      
        
          
          
            


  <section class='widget music'>
    
<header class='pure'>
  <div><i class="fas fa-compact-disc fa-fw" aria-hidden="true"></i>&nbsp;&nbsp;最近在听</div>
  
    <a class="rightBtn"
    
      rel="external nofollow noopener noreferrer"
    
    
      target="_blank"
    
    href="https://music.163.com/#/user/home?id=1960721923"
    title="https://music.163.com/#/user/home?id=1960721923">
    <i class="far fa-heart fa-fw"></i></a>
  
</header>

    <div class='content pure'>
      
  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer@1.7.0/dist/APlayer.min.css">
  <div class="aplayer"
    data-theme="#1BCDFC"
    
    
    data-mode="circulation"
    data-server="netease"
    data-type="playlist"
    data-id="2957571193"
    data-volume="0.7">
  </div>
  <script src="https://cdn.jsdelivr.net/npm/aplayer@1.7.0/dist/APlayer.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/meting@1.1.0/dist/Meting.min.js"></script>


    </div>
  </section>


          
        
      
    

  
</aside>

<footer id="footer" class="clearfix">
  <div id="sitetime"></div>
  
  
    <div class="social-wrapper">
      
        
          <a href="/atom.xml"
            class="social fas fa-rss flat-btn"
            target="_blank"
            rel="external nofollow noopener noreferrer">
          </a>
        
      
        
          <a href="mailto:rogerspy@163.com"
            class="social fas fa-envelope flat-btn"
            target="_blank"
            rel="external nofollow noopener noreferrer">
          </a>
        
      
        
          <a href="https://github.com/rogerspy"
            class="social fab fa-github flat-btn"
            target="_blank"
            rel="external nofollow noopener noreferrer">
          </a>
        
      
        
          <a href="https://music.163.com/#/user/home?id=1960721923"
            class="social fas fa-headphones-alt flat-btn"
            target="_blank"
            rel="external nofollow noopener noreferrer">
          </a>
        
      
    </div>
  
  <br>
  <div><p>博客内容遵循 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议</a></p>
</div>
  <div>
    本站使用
    <a href="https://xaoxuu.com/wiki/material-x/" target="_blank" class="codename">Material X</a>
    作为主题
    
      ，
      总访问量为
      <span id="busuanzi_value_site_pv"><i class="fas fa-spinner fa-spin fa-fw" aria-hidden="true"></i></span>
      次
    
    。
  </div>
	</footer>

<script>setLoadingBarProgress(80);</script>
<!-- 点击特效，输入特效 运行时间 -->
<script type="text/javascript" src="/cool/cooltext.js"></script>
<script type="text/javascript" src="/cool/clicklove.js"></script>
<script type="text/javascript" src="/cool/sitetime.js"></script>



      <script>setLoadingBarProgress(60);</script>
    </div>
    <a class="s-top fas fa-arrow-up fa-fw" href='javascript:void(0)'></a>
  </div>
  <script src="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js"></script>

  <script>
    var GOOGLE_CUSTOM_SEARCH_API_KEY = "";
    var GOOGLE_CUSTOM_SEARCH_ENGINE_ID = "";
    var ALGOLIA_API_KEY = "";
    var ALGOLIA_APP_ID = "";
    var ALGOLIA_INDEX_NAME = "";
    var AZURE_SERVICE_NAME = "";
    var AZURE_INDEX_NAME = "";
    var AZURE_QUERY_KEY = "";
    var BAIDU_API_ID = "";
    var SEARCH_SERVICE = "hexo" || "hexo";
    var ROOT = "/"||"/";
    if(!ROOT.endsWith('/'))ROOT += '/';
  </script>

<script src="//instant.page/1.2.2" type="module" integrity="sha384-2xV8M5griQmzyiY3CDqh1dn4z3llDVqZDqzjzcY+jCBCk/a5fXJmuZ/40JJAPeoU"></script>


  <script async src="https://cdn.jsdelivr.net/npm/scrollreveal@4.0.5/dist/scrollreveal.min.js"></script>
  <script type="text/javascript">
    $(function() {
      const $reveal = $('.reveal');
      if ($reveal.length === 0) return;
      const sr = ScrollReveal({ distance: 0 });
      sr.reveal('.reveal');
    });
  </script>


  <script src="https://cdn.jsdelivr.net/npm/node-waves@0.7.6/dist/waves.min.js"></script>
  <script type="text/javascript">
    $(function() {
      Waves.attach('.flat-btn', ['waves-button']);
      Waves.attach('.float-btn', ['waves-button', 'waves-float']);
      Waves.attach('.float-btn-light', ['waves-button', 'waves-float', 'waves-light']);
      Waves.attach('.flat-box', ['waves-block']);
      Waves.attach('.float-box', ['waves-block', 'waves-float']);
      Waves.attach('.waves-image');
      Waves.init();
    });
  </script>


  <script async src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-busuanzi@2.3/js/busuanzi.pure.mini.js"></script>




  
  
  
    <script src="https://cdnjs.cloudflare.com/ajax/libs/jquery-backstretch/2.0.4/jquery.backstretch.min.js"></script>
    <script type="text/javascript">
      $(function(){
        if ('.cover') {
          $('.cover').backstretch(
          ["https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/a0c9e6f9efad8b731cb7376504bd10d79d2053.jpg"],
          {
            duration: "6000",
            fade: "2500"
          });
        } else {
          $.backstretch(
          ["https://cdn.jsdelivr.net/gh/rogerspy/blog-imgs/a0c9e6f9efad8b731cb7376504bd10d79d2053.jpg"],
          {
            duration: "6000",
            fade: "2500"
          });
        }
      });
    </script>
  







  <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.css">
  <script src="https://cdn.jsdelivr.net/npm/gitalk@1/dist/gitalk.min.js"></script>
  <script type="text/javascript">
    var gitalk = new Gitalk({
      clientID: "35a5e4dc744cc7d162af",
      clientSecret: "7b5a409e17ce0c1971f284eac9f8902eb4b8feba",
      repo: "rogerspy.github.io",
      owner: "Rogerspy",
      admin: "Rogerspy",
      
        id: "/wiki/material-x/",
      
      distractionFreeMode: false  // Facebook-like distraction free mode
    });
    gitalk.render('gitalk-container');
  </script>





  <script src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-material-x@19.5/js/app.js"></script>


  <script src="https://cdn.jsdelivr.net/gh/xaoxuu/cdn-material-x@19.5/js/search.js"></script>




<!-- 复制 -->
<script src="https://cdn.jsdelivr.net/npm/clipboard@2/dist/clipboard.min.js"></script>
<script>
  let COPY_SUCCESS = "复制成功";
  let COPY_FAILURE = "复制失败";
  /*页面载入完成后，创建复制按钮*/
  !function (e, t, a) {
    /* code */
    var initCopyCode = function(){
      var copyHtml = '';
      copyHtml += '<button class="btn-copy" data-clipboard-snippet="">';
      copyHtml += '  <i class="fa fa-copy"></i><span>复制</span>';
      copyHtml += '</button>';
      $(".highlight .code pre").before(copyHtml);
      var clipboard = new ClipboardJS('.btn-copy', {
        target: function(trigger) {
          return trigger.nextElementSibling;
        }
      });

      clipboard.on('success', function(e) {
        //您可以加入成功提示
        console.info('Action:', e.action);
        console.info('Text:', e.text);
        console.info('Trigger:', e.trigger);
        success_prompt(COPY_SUCCESS);
        e.clearSelection();
      });
      clipboard.on('error', function(e) {
        //您可以加入失败提示
        console.error('Action:', e.action);
        console.error('Trigger:', e.trigger);
        fail_prompt(COPY_FAILURE);
      });
    }
    initCopyCode();

  }(window, document);

  /**
   * 弹出式提示框，默认1.5秒自动消失
   * @param message 提示信息
   * @param style 提示样式，有alert-success、alert-danger、alert-warning、alert-info
   * @param time 消失时间
   */
  var prompt = function (message, style, time)
  {
      style = (style === undefined) ? 'alert-success' : style;
      time = (time === undefined) ? 1500 : time*1000;
      $('<div>')
          .appendTo('body')
          .addClass('alert ' + style)
          .html(message)
          .show()
          .delay(time)
          .fadeOut();
  };

  // 成功提示
  var success_prompt = function(message, time)
  {
      prompt(message, 'alert-success', time);
  };

  // 失败提示
  var fail_prompt = function(message, time)
  {
      prompt(message, 'alert-danger', time);
  };

  // 提醒
  var warning_prompt = function(message, time)
  {
      prompt(message, 'alert-warning', time);
  };

  // 信息提示
  var info_prompt = function(message, time)
  {
      prompt(message, 'alert-info', time);
  };

</script>


<!-- fancybox -->
<script src="https://cdn.jsdelivr.net/gh/fancyapps/fancybox@3.5.7/dist/jquery.fancybox.min.js"></script>
<script>
  let LAZY_LOAD_IMAGE = "";
  $(".article-entry").find("fancybox").find("img").each(function () {
      var element = document.createElement("a");
      $(element).attr("data-fancybox", "gallery");
      $(element).attr("href", $(this).attr("src"));
      /* 图片采用懒加载处理时,
       * 一般图片标签内会有个属性名来存放图片的真实地址，比如 data-original,
       * 那么此处将原本的属性名src替换为对应属性名data-original,
       * 修改如下
       */
       if (LAZY_LOAD_IMAGE) {
         $(element).attr("href", $(this).attr("data-original"));
       }
      $(this).wrap(element);
  });
</script>





  <script>setLoadingBarProgress(100);</script>
</body>
</html>
